蟻本2-5 Layout - 競プロ

蟻本2-5 Layout

code: python

import sys

MAX_N = 1000

MAX_ML = 10000

MAX_MD = 10000

INF = float('inf')

# 入力

N, ML, MD = map(int,input().split())

AL = 0 * MAX_ML

BL = 0 * MAX_ML

DL = 0 * MAX_ML

for i in range(ML):

ALi, BLi, DLi = map(int,input().split())

AD = 0 * MAX_MD

BD = 0 * MAX_MD

DD = 0 * MAX_MD

for i in range(MD):

ADi, BDi, DDi = map(int,input().split())

d = 0 * MAX_N # 最短距離

updated = False # 更新されたか

def update(x, y, i):

global updated

if x > y:

di = y

updated = True

# ベルマンフォード法によりdを計算する

def bellmanford():

global updated

for k in range(N + 1):

updated = False

# i+1からiへコスト0

for i in range(N):

if di + 1 < INF:

update(di, di + 1, i)

# ALからBLへコストDL

for i in range(ML):

if d[ALi - 1] < INF:

update(d[BLi - 1], d[ALi - 1] + DLi, BLi - 1)

# BDからADへコスト-DD

for i in range(MD):

if d[BDi - 1] < INF:

update(d[ADi - 1], d[BDi - 1] - DDi, ADi - 1)

# 負閉路チェック

bellmanford()

if updated:

print(-1)

sys.exit() # ここでプログラムを終了

d = INF * MAX_N

d0 = 0

bellmanford()

res = dN - 1

if res == INF:

res = -2

print(res)

# 4 2 1

# 1 3 10

# 2 4 20

# 2 3 3

テーマ